The invention relates generally to an improved method for reading two-dimensional barcodes printed within an image. In particular, the method of reading two-dimensional barcodes of the present invention provides improved performance when reading documents which have been previously transmitted by facsimile, or which contain noise similar to that caused by facsimile machines.
A common technique for reading raw bits (i.e., logical bits representing either a xe2x80x9c1xe2x80x9d or a xe2x80x9c0xe2x80x9d) in a one-dimensional barcode is to move a horizontal scan line across the barcode and detect transitions from white to black and from black to white. However, this technique cannot be directly applied to a two-dimensional barcode which consists of an array of N rows and M columns of logical bits, because a single scan line can not determine which of the N rows or which of the M columns it is reading.
Various techniques have been used to read the logical bits from a two-dimensional barcode which involve the addition of alignment marks and/or clock bits that are used to specifically identify the separate rows and columns.
A method of reading a two-dimensional barcode which does not require clock bits or alignment marks to identify rows or columns of logical bits is described in U.S. Pat. No. 5,862,270 (xe2x80x9cthe ""270 Patentxe2x80x9d), entitled xe2x80x9cA Clock-Free Two-Dimensional Barcode and Method for Printing and Reading the Samexe2x80x9d and assigned to the same assignee as the present invention. The contents of the ""270 Patent are explicitly incorporated by reference herein. As described in further detail in the ""270 Patent, the method for reading the logical bits within a two-dimensional barcode described therein operates on the bit array resulting from the scanning process. All of the horizontal xe2x80x9cedgesxe2x80x9d for each column of the pixel array, and all of the vertical xe2x80x9cedgesxe2x80x9d for each row are identified and then counted, and then horizontal and vertical histograms (actually one-dimensional arrays) are created of the edge count for each column and row, respectively. Each array is then examined to determine the local minimas, which represent the center lines for each column and row, since there are much fewer edges in the center of a column or row than at the periphery. Since the system has a priori knowledge of how many logical bits are in a column and in a row (and thus how far apart the column and row centerlines should be), the processing of these one-dimensional arrays is improved by only looking within particular regions for the local minimas.
However, the method of the ""270 Patent may encounter difficulties in reading a two-dimensional barcode which has been transmitted by facsimile, due to distortion of the barcode caused by horizontal line drop and horizontal line repeat during the facsimile transmission of the document, or a two-dimensional barcode which contains drawn line noise in either the horizontal or vertical directions. A horizontal line drop, when it occurs at the point on the document being transmitted where the barcode is positioned, causes the height of a row of logical bits to be smaller than the height of the rest of the rows within the two-dimensional barcode. Of course, as one reasonably skilled in the art will recognize, if the horizontal line drop is so large that an entire row of logical bits is deleted, no amount of processing can read the deleted logical bits, although, as discussed in the ""270 Patent, error correction techniques may be used to recover the lost data. On the other hand, a horizontal line repeat, when it occurs at the point on the document being transmitted where the barcode is positioned, causes the height of one row of logical bits to be larger than the height of the rest of the rows and the height of another row of logical bits to be smaller than the height of the rest of the rows within the two-dimensional barcode. Drawn line noise is caused by actual marking of the document by, e.g., a pencil, and can cause a single row or column of logical bits to appear as two separate rows or columns of logical bits having a height or width, respectively, smaller than the rest of the rows or columns.
The method of ""270 Patent may miss a row centerline, add a row centerline, or both, due to line repeat or line drop distortion, since both types of distortion cause the center line for the row distorted to have an unanticipated row to row spacing. In FIG. 1, a barcode 10 which has suffered a line drop of four lines is shown alongside the resulting vertical edge histogram 20 (histograms are used herein to graphically display the horizontal (or column) and vertical (or row) edge count arrays which are processed to locate the column and row centerlines, respectively). The row centerlines 30 through 60 and 80 have been determined by the method of the ""270 Patent. While row centerlines 30, 40, 50 and 80 have been correctly determined, centerline 60 was incorrectly determined due to the extra local minima caused by the line drop and is thus too close to centerline 50. In addition, local minima 70, representing the proper centerline for that row, was missed since it was not within the region examined for a local minima.
It is therefore an object of the present invention to provide an improved method of reading a clock free two-dimensional barcode printed on a printed medium.
It is an additional object of this invention to provide a method of reading a clock free two-dimensional barcode which includes distortion caused by the transmission by facsimile of the document on which the barcode is printed.
It is yet another object of this invention to provide a method of reading a clock free two-dimensional barcode which includes distortion caused by lines drawn on the face of the document on which the barcode is printed.
Various other objects, advantages and features of the present invention will become readily apparent from the ensuing detailed description and the novel features will be particularly pointed out in the appended claims.
The present invention is directed to a method of decoding information stored in a two-dimensional barcode printed on a printed medium which provides improved performance when the barcode to be read includes line drop or line repeat distortion caused by transmission by facsimile. Two embodiments of the present invention are disclosed. In both embodiments, the two-dimensional barcode is first scanned to create a two-dimensional pixel array representing the two-dimensional barcode. Then the number of horizontal edges in each column of pixels in the two-dimensional pixel array are determined and stored in an horizontal edge count array, and, likewise, the number of vertical edges in each row of pixels in the two-dimensional pixel array are determined and stored in a vertical edge count array. Each array is then processed to locate the centerlines therein, where the intersection of each column and row centerline represents the position of a binary bit of data stored in the two-dimensional barcode. The centerlines are then used to extract the binary data from the scanned two-dimensional barcode, to produce a signal representative of the encoded information stored therein.
In the first embodiment, the horizontal and vertical edge count arrays are processed in the same manner to extract the column and row centerlines, respectively. In particular, each of the two edge count arrays is separately scanned to determine the centerlines therein by locating each successive pair of peaks in the edge counts, each of the peaks having a magnitude greater than a first predetermined value, and then locating a centerline in a valley region between each successive pair of peaks, each of the centerlines having a magnitude less than a second predetermined value. Once both edge count arrays have been processed, the binary data located at the intersection of each row centerline and column centerline is read to produce a signal representative of the encoded information in the two-dimensional barcode. Preferably, each of the successive pair of peaks in the edge count array must be separated by a third predetermined value. In addition, the first predetermined value is preferably reduced by a predetermined amount if a second peak within a pair of peaks in the edge count array is separated from a first peak by more than a fourth predetermined value, and the second peak is then reidentified using the reduced first predetermined value.
In the second embodiment, the horizontal and vertical edge arrays are processed differently to extract the centerlines therein, to reduce the number of total errors encountered when using the method of the first embodiment. Since it is more likely that line drop or line repeat distortion will affect the row centerline spacing than the column centerline spacing, the horizontal edge array is first processed using the prior art method (i.e., the method disclosed in the ""270 Patent), in which the local minima representing the column centerlines in the horizontal edge counts are located. If the number of column centerlines located conforms to the expected value, processing proceeds to the vertical edge array. However, if the number of column centerlines located is not equal to the expected value, the column centerlines are alternately determined using the method of the first embodiment, in which each successive pair of peaks in the horizontal edge counts is located, each of the peaks having a magnitude greater than a first predetermined value, and then locating a column centerline in a valley region between each successive pair of peaks, each of the column centerlines having a magnitude less than a second predetermined value. The vertical edge count array is processed differently, first employing the method of the first embodiment in which the row centerlines are determined by locating each successive pair of peaks in the vertical edge counts, each of the peaks having a magnitude greater than the first predetermined value, and then locating a row centerline in a valley region between each successive pair of peaks, each of the row centerlines having a magnitude less than a second predetermined value. If the number of row centerlines located thereby conforms to the expected value, processing is complete and the encoded information can be read from the scanned barcode. However, if the number of row centerlines located is one greater than the expected value, the extra centerline is located and deleted. Also, if the number of row centerlines located is one less than the expected value, the missing centerline is located and inserted. In addition, if the number of row centerlines is more than one greater than the expected value or more than one less than the expected value, the row centerlines are alternately located by locating the local minima representing the row centerlines in the vertical edge counts. Once the column and row centerlines have been correctly determined, the binary data located at the intersection of each row centerline and column centerline is read to produce a signal representative of the encoded information in the two-dimensional barcode.